package heap;

import edu.princeton.cs.algs4.MinPQ;

public class HuffManEncode {
    private MinPQ<MyChar> minPQ;

    /**
     * 构造方法，通过MyChar数组构造最小堆
     * @param myChars
     */
    public HuffManEncode(MyChar[] myChars){
        minPQ = new MinPQ<>(myChars);
    }

    /**
     * 进行huffman编码，每次合并两个最小权重
     * @return
     */
    public MyChar getEncode(){
        while(minPQ.size() != 1){
            MyChar a = minPQ.delMin();
            MyChar b = minPQ.delMin();
            MyChar newNode = new MyChar(' ', a.getWeight()+b.getWeight());
            newNode.setLeft(a);
            newNode.setRight(b);
            minPQ.insert(newNode);
        }
        return minPQ.delMin();
    }
}

class MyChar implements Comparable<MyChar>{
    private char ch;
    private int weight;
    private MyChar left;
    private MyChar right;

	@Override
	public int compareTo(MyChar mChar) {
		return Integer.compare(this.weight, mChar.weight);
    }

    public MyChar() {
    }

    public MyChar(char ch, int weight) {
        this.ch = ch;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "MyChar [ch=" + ch + ", left=" + left + ", right=" + right + ", weight=" + weight + "]";
    }

    public char getCh() {
        return ch;
    }

    public void setCh(char ch) {
        this.ch = ch;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public MyChar getLeft() {
        return left;
    }

    public void setLeft(MyChar left) {
        this.left = left;
    }

    public MyChar getRight() {
        return right;
    }

    public void setRight(MyChar right) {
        this.right = right;
    }

    
    
}